Ternary Content-Addressable Memories (TCAMs) are becoming very popular for designing high-throughput forwarding engines on routers—they are fast, cost-effective and simple to manage. Specifically, TCAMs are fully associative memories that allow a “don't care” state to be stored in each memory cell in addition to 0s and 1. This feature makes them particularly attractive for packet classification and route lookup applications that require longest prefix matches. For example, when a destination address is presented to the TCAM, each TCAM entry may be looked up in parallel, and the longest prefix that matches the address is returned. Thus, a single TCAM access is sufficient to perform a complete route lookup operation. In contrast, conventional ASIC-based designs that use routing tries may require many memory accesses for a single route lookup. (As is well known to those skilled in the art, a routing trie is a tree-based data structure used to store routing prefixes for use in longest prefix matching.) Thus, routing latencies for TCAM-based routing tables are significantly lower than they are for ASIC-based tables. Moreover, TCAM-based tables are typically much easier to manage and update than tables implemented using tries.
Despite these advantages, routing vendors have been slow in adopting TCAM devices in packet forwarding engines for at least two reasons. First, TCAM devices have traditionally been more expensive and less dense compared to conventional ASIC-based devices. However, both the density and the cost of TCAMs have dramatically improved in the past few years, making them a viable alternative to ASIC-based designs in high-speed core routers. The second reason is that of high power consumption. Current high-density TCAM devices consume as much as 12 to 15 Watts each when all of the TCAM memory entries are enabled for search. Moreover, a single linecard may require multiple TCAMs to handle filtering and classification as well as IP lookups on large forwarding tables. This high power consumption number affects costs in two ways—first, it increases power supply and cooling costs that account for a significant portion of the operational expenses for an ISP (Internet Service Provider), and second, it reduces port density since higher power consumption implies that fewer ports can be packed into the same space (e.g., a router rack) due to cooling constraints. Therefore, it is important to significantly reduce the power requirements of TCAM-based forwarding engines (and other lookup engines) to make them economically viable.